import copy

from Board import Board
from ai_alg_struct import *
from Frame import Frame

'''
该模组定义诸多实现算法, 用于生成步伐
'''


def Monte_Carlo(board: Board):
    dir, x, y = [int(i) for i in input().split()]

    return dir, x, y

def bian(board,i,j):
    f1 = 0
    f2 = 0
    f3 = 0
    f4 = 0
    if i<=4 and j<=4:
        if board.line[0][i][j] != 0:
            f1 = 1
        if board.line[0][i + 1][j] != 0:
            f2 = 1
        if board.line[1][j][i] != 0:
            f3 = 1
        if board.line[1][j + 1][i] != 0:
            f4 = 1
        return f1+f2+f3+f4


# 测试蠢蛋AI
def Cupidity(frame: Frame):
    board = copy.deepcopy(frame.current_board)
    tree = TreeNode(frame.red_player, frame.blue_player, frame.red_score, frame.blue_score, frame.current_round,
                    board, None)
    tree.control_deep()
    # 这里返回的是将要下的可用边，已经经过第一次评估
    steps = tree.get_best_step()
    # 这里存放最佳的可用边
    best_step = []
    best_step_three = []
    # 这里用来存放备选步数
    alternative_step = []
    flag1 = 0
    # 这里获取当前步数的最佳步伐有几个
    line = board.line
    box = board.box
    # 对可用边进行迭代
    for step in steps:
        dir_new = step[0]
        x_new = step[1]
        y_new = step[2]
        # 判断可用边将下在什么地方
        for i in range(0, 5):
            for j in range(0, 5):
                # 当前格子被捕获，不需要判断了
                if box[i][j] != 0:
                    continue
                # 为格子上边
                if dir_new == 0 and x_new == i and y_new == j:
                    flag1 = 1
                # 为格子下边
                elif dir_new == 0 and x_new == i + 1 and y_new == j:
                    flag1 = 1
                # 为格子左边
                elif dir_new == 1 and x_new == j and y_new == i:
                    flag1 = 1
                # 为格子右边
                elif dir_new == 1 and x_new == j + 1 and y_new == i:
                    flag1 = 1
                box_x = -1
                box_y = -1
                # 表面这个边应该落在这个格子里面
                if flag1 == 1:
                    box_x = i
                    box_y = j
                else:
                    dir = 1
                    x = j + 1
                    y = i
                score = 100
                flag1 = 0
                flag2 = 0
                flag3 = 0
                flag4 = 0
                continue
            # 其次搜索空白区域，可衍生到旁边格子，暂时不需要衍生
            # 默认是返回左边的坐标
            if (flag1 + flag2 + flag3 + flag4 == 0) and score < 80:
                if bian(board,i,j)<=1:
                    dir = 0
                    x = i
                    y = j
                    score=80
                    flag1 = 0
                    flag2 = 0
                    flag3 = 0
                    flag4 = 0
                    continue
                if bian(board,i+1,j)<=1:
                    dir=0
                    x=i+1
                    y=j
                    score=80
                    flag1 = 0
                    flag2 = 0
                    flag3 = 0
                    flag4 = 0
                    continue
                if bian(board,j,i)<=1:
                    dir=1
                    x=j
                    y=i
                    score=80
                    flag1 = 0
                    flag2 = 0
                    flag3 = 0
                    flag4 = 0
                    continue
                if bian(board,j+1,i)<=1:
                    dir=1
                    x=j+1
                    y=i
                    score=80
                    flag1 = 0
                    flag2 = 0
                    flag3 = 0
                    flag4 = 0
                    continue
            # 其次是一个边的，默认返回它的对边
            if (flag1 + flag2 + flag3 + flag4 == 1) and score < 60:
                if i<4 and j<4:
                  if flag1 == 1:
                      if bian(board,i+1,j)<=1:
                          dir = 0
                          x = i + 1
                          y = j
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                      if bian(board,j,i)<=1:
                          dir=1
                          x=j
                          y=i
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                      if bian(board,j+1,i)<=1:
                          dir=1
                          x=j+1
                          y=i
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                  elif flag2 == 1:
                      if bian(board,i,j)<=1:
                          dir = 0
                          x = i
                          y = j
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                      if bian(board,j,i)<=1:
                          dir=1
                          x=j
                          y=i
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                      if bian(board,j+1,i)<=1:
                          dir=1
                          x=j+1
                          y=i
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                  elif flag3 == 1:
                      if bian(board,j+1,i)<=1:
                          dir = 1
                          x = j + 1
                          y = i
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                      if bian(board,i,j)<=1:
                          dir=0
                          x=i
                          y=j
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                      if bian(board,i+1,j):
                          dir=0
                          x=i+1
                          y=j
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                  else:
                      if bian(board,j,i)<=1:
                          dir = 1
                          x = j
                          y = i
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                      if bian(board,i,j)<=1:
                          dir=0
                          x=i
                          y=j
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                      if bian(board,i+1,j)<=1:
                          dir=0
                          x=i+1
                          y=j
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                elif i==4 and j<4:
                  if flag1==1:
                      if bian(board,i,j)<=1:
                          dir=0
                          x=i+1
                          y=j
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                elif i==4 and j==4:
                  if flag1==1:
                      if bian(board,i,j)<=1:
                          dir=0
                          x=i+1
                          y=j
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                      if bian(board,i,j-1)<=1:
                          dir=1
                          x=i
                          y=j-1
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                  if flag2==1:
                      if bian(board,i-1,j)<=1:
                          dir=0
                          x=i
                          y=j
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                      if bian(board,i,j-1)<=1:
                          dir=1
                          x=j
                          y=i
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
                      if bian(board,i,j)<=1:
                          dir=1
                          x=j+1
                          y=i
                          score = 60
                          flag1 = 0
                          flag2 = 0
                          flag3 = 0
                          flag4 = 0
                          continue
            # 最后是两个边的，最后的选择
            if (flag1 + flag2 + flag3 + flag4 == 2) and score < 40:
                if flag1 + flag2 == 2:
                    dir = 1
                    x = j
                    y = i
                elif flag1 + flag3 == 2 or flag1 + flag4 == 2:
                    dir = 0
                    x = i + 1
                    y = j
                elif flag2 + flag3 == 2 or flag2 + flag4 == 2:
                    dir = 0
                    x = i
                    y = j
                else:
                    dir = 0
                    x = i
                    y = j
                score = 40
                flag1 = 0
                flag2 = 0
                flag3 = 0
                flag4 = 0
                continue
                # 用来存放当前格子空闲的边的坐标
                # box_steps = board.get_captured_line(box_x, box_y)
                # point = len(box_steps)
                point = board.get_line_count(box_x, box_y)
                # 当没有边被占领的时候
                if point == 0:
                    flag1 = 0
                    # 这时较为宽松，我们应该致力于让2分的格子多
                    # 所以这里优选判断当前2分的格子
                    if (board.get_box_count(0) + board.get_box_count(1)) * 5 - board.get_box_count(2) * 10 >= 10:
                        if not ((dir_new, x_new, y_new) in best_step):
                            best_step.append((dir_new, x_new, y_new))
                        continue
                # 当为1条边被占的时候
                if point == 1:
                    flag1 = 0
                    # 这里需要侧重判断3和2分的数量，但更加侧重于3
                    if (board.get_box_count(0) + board.get_box_count(1)) * 5 - (
                            board.get_box_count(3) * (2 / 3) + board.get_box_count(2) * (1 / 3)) * 10 >= 10:
                        if not ((dir_new, x_new, y_new) in best_step):
                            best_step.append((dir_new, x_new, y_new))
                        continue
                # 当有两条边被占的时候
                if point == 2:
                    flag1 = 0
                    # 此时这个边将围成c型格，所以需要考虑是否为后面的步伐考虑
                    # 小于等于30说明此时后面的格子2格至少有4个，那么即使对面再吃一分，我也可以吃2分，不亏也不赚这是最差的结果
                    # 这里完全只考虑2和3分的策略问题
                    if board.get_box_count(3) * 30 - board.get_box_count(2) * 15 <= -30:
                        if not ((dir_new, x_new, y_new) in best_step):
                            best_step.append((dir_new, x_new, y_new))
                        continue
                if point == 3:
                    flag1 = 0
                    # 此时进行下边的话，虽然会得到一分，但是会多出来一步，如果后面的2边大于现在的数目的收益，那将是有风险的
                    # 若大于等于30 表示后面至少有4分可以得
                    if not ((dir_new, x_new, y_new) in best_step_three):
                        best_step_three.append((dir_new, x_new, y_new))
                    # if board.get_box_count(3) * 15 - board.get_box_count(2) * 30 >= 30:
                    #     if not ((dir_new, x_new, y_new) in best_step):
                    #         best_step.append((dir_new, x_new, y_new))
                    continue
                # 如果上面的条件都没满足，那么说明当前局势对我们的不怎么有利那么我们就构造有利的局面
                # 比如说，我们需要构造多个2分的格子后面便于我们进行吃但这个2分的格子只需要简单的考虑当前格子的分数，给定一个预估值进行我们的预期判断即可，不必进行周边搜索
                # 不管当前得分
                # 到这里经过了整个循环，说明当前步数不利，进入备选步数
                flag1 = 0
                if not ((dir_new, x_new, y_new) in alternative_step):
                    alternative_step.append((dir_new, x_new, y_new))
    if len(best_step) == 0 and len(best_step_three) == 0:
        steps = alternative_step
        length = len(steps)
        if len(steps) == 1:
            step = steps[0]
            dir = step[0]
            x = step[1]
            y = step[2]
        else:
            step = steps[random.randint(0, len(steps) - 1)]
            dir = step[0]
            x = step[1]
            y = step[2]
    elif len(best_step_three) != 0:
        steps = best_step_three
        length = len(steps)
        if len(steps) == 1:
            step = steps[0]
            dir = step[0]
            x = step[1]
            y = step[2]
        else:
            step = steps[random.randint(0, len(steps) - 1)]
            dir = step[0]
            x = step[1]
            y = step[2]
    else:
        steps = best_step
        length = len(steps)
        if len(steps) == 1:
            step = steps[0]
            dir = step[0]
            x = step[1]
            y = step[2]
        else:
            step = steps[random.randint(0, len(steps) - 1)]
            dir = step[0]
            x = step[1]
            y = step[2]
    return dir, x, y


# 估值函数
def estimate(current_round, valid_step, red_score, blue_score, red_player, blue_player, win):
    score = 0
    if current_round == red_player:
        if red_score > blue_score:
            score += 2
        else:
            score -= 2
        if len(valid_step) <= 31:
            score += 1
        else:
            score -= 1
    else:
        if blue_score > red_score:
            score += 2
        else:
            score -= 2
        if len(valid_step) <= 31:
            score += 1
        else:
            score -= 1
    if win == current_round:
        score += 3
    else:
        score -= 3
    return score


# 判断短链
def jg_sc(board: Board):
    # ******
    # 特殊情况
    # ******
    # 左上角横向
    top_left_t = 0
    # 左上角纵向
    top_left_l = 0
    # 若top_left == 1 表示左上角横向的长链形成
    if board.line[0][0][0] != 0 and board.line[0][0][1] != 0 and board.line[0][1][0] != 0 and board.line[0][1][
        1] != 0 and board.line[1][0][0] == 0 and board.line[1][1][0] == 0 and board.line[1][2][0] == 0:
        top_left_t = 1
    if board.line[1][0][0] != 0 and board.line[1][0][1] != 0 and board.line[1][1][0] != 0 and board.line[1][1][
        1] != 0 and board.line[0][0][0] == 0 and board.line[0][1][0] == 0 and board.line[0][2][0] == 0:
        top_left_l = 1
    # 右上角横向
    top_right_t = 0
    # 右上角纵向
    top_right_l = 0
    if board.line[0][0][3] != 0 and board.line[0][0][4] != 0 and board.line[0][1][3] != 0 and board.line[0][1][
        4] != 0 and board.line[1][3][0] == 0 and board.line[1][4][0] == 0 and board.line[1][5][0] == 0:
        top_right_t = 1
    if board.line[1][4][0] != 0 and board.line[1][4][1] != 0 and board.line[1][5][0] != 0 and board.line[1][5][
        1] != 0 and board.line[0][0][4] == 0 and board.line[0][1][4] == 0 and board.line[0][2][4] == 0:
        top_right_l = 1
    # 左下角横向
    bottom_left_t = 0
    # 左下角纵向
    bottom_left_l = 0
    if board.line[0][4][0] != 0 and board.line[0][4][1] != 0 and board.line[0][5][0] != 0 and board.line[0][5][
        1] != 0 and board.line[1][0][4] == 0 and board.line[1][1][4] == 0 and board.line[1][1][4] == 0:
        bottom_left_t = 1
    if board.line[1][0][3] != 0 and board.line[1][0][4] != 0 and board.line[1][1][3] != 0 and board.line[1][1][
        4] != 0 and board.line[0][3][0] == 0 and board.line[0][4][0] == 0 and board.line[0][5][0] == 0:
        bottom_left_l = 1
    # 右下角横向
    bottom_right_t = 0
    # 右下角纵向
    bottom_right_l = 0
    if board.line[0][4][3] != 0 and board.line[0][4][4] != 0 and board.line[0][5][3] != 0 and board.line[0][5][
        4] != 0 and board.line[1][3][4] == 0 and board.line[1][4][4] == 0 and board.line[1][5][4] == 0:
        bottom_right_t = 1
    if board.line[1][4][3] != 0 and board.line[1][4][4] != 0 and board.line[1][5][3] != 0 and board.line[1][5][
        4] != 0 and board.line[0][3][4] == 0 and board.line[0][4][4] == 0 and board.line[0][5][4] == 0:
        bottom_right_l = 1
    # 循环判断上面横向的短链(横向需要判断2个）
    top_all_t = 0
    for i in range(1, 2):
        if board.line[0][0][i] != 0 and board.line[0][0][i + 1] != 0 and board.line[0][1][i] != 0 and board.line[0][1][
            i + 1] != 0 and board.line[1][i][0] == 0 and board.line[1][i + 1][0] == 0 and board.line[1][i + 2][0] == 0:
            top_all_t += 1
    # 循环判断上面纵向的短链（纵向需要判断3个）
    top_all_l = 0
    for j in range(1, 3):
        if board.line[1][j][0] != 0 and board.line[1][j][1] != 0 and board.line[1][j + 1][0] != 0 and \
                board.line[1][j + 1][1] != 0 and board.line[0][0][j] == 0 and board.line[0][1][j] == 0 and \
                board.line[0][2][j] == 0:
            top_all_l += 1
    # 循环判断下面横向的短链（横向需要判断2个）
    bottom_all_t = 0
    for i in range(1, 2):
        if board.line[0][4][i] != 0 and board.line[0][4][i + 1] != 0 and board.line[0][5][i] != 0 and board.line[0][5][
            i + 1] != 0 and board.line[1][i][4] == 0 and board.line[1][i + 1][4] == 0 and board.line[1][i + 2][4] == 0:
            bottom_all_t += 1
    # 循环判断下面纵向的短链（纵向需要判断3个）
    bottom_all_l = 0
    for j in range(1, 3):
        if board.line[1][j][3] != 0 and board.line[1][j][4] != 0 and board.line[1][j + 1][3] != 0 and \
                board.line[1][j + 1][4] != 0 and board.line[0][3][j] == 0 and board.line[0][4][j] == 0 and \
                board.line[0][5][j] == 0:
            bottom_all_l += 1
    # 循环判断左侧横向的短链（横向需要判断3个）
    left_all_t = 0
    for k in range(1, 3):
        if board.line[0][k][0] != 0 and board.line[0][k][1] != 0 and board.line[0][k + 1][0] != 0 and \
                board.line[0][k + 1][1] != 0 and board.line[1][0][k] == 0 and board.line[1][1][k] == 0 and \
                board.line[1][2][k] == 0:
            left_all_t += 1
    # 循环判断左侧纵向的短链 (纵向的需要2个）
    left_all_l = 0
    for l in range(1, 2):
        if board.line[1][0][l] != 0 and board.line[1][0][l + 1] != 0 and board.line[1][1][l] != 0 and board.line[1][1][
            l + 1] != 0 and board.line[0][l][0] == 0 and board.line[0][l + 1][0] == 0 and board.line[0][l + 2][0] == 0:
            left_all_l += 1
    # 循环判断右侧横向的短链（横向需要判断3个）
    right_all_t = 0
    for k in range(1, 3):
        if board.line[0][k][3] != 0 and board.line[0][k][4] != 0 and board.line[0][k + 1][3] != 0 and \
                board.line[0][k + 1][4] != 0 and board.line[1][3][k] == 0 and board.line[1][4][k] == 0 and \
                board.line[1][5][k] == 0:
            right_all_t += 1
    # 循环判断右侧纵向的短链（纵向需要判断2个）
    right_all_l = 0
    for l in range(1, 2):
        if board.line[1][4][l] != 0 and board.line[1][4][l + 1] != 0 and board.line[1][5][l] != 0 and board.line[1][5][
            l + 1] != 0 and board.line[0][l][4] == 0 and board.line[0][l + 1][4] == 0 and board.line[0][l + 2][4] == 0:
            right_all_l += 1
    # 循环判断中间部分横向的短链 （横向需要判断3行2个）
    mid_all_t = 0
    for i in range(1, 3):
        for j in range(1, 2):
            if board.line[0][i][j] != 0 and board.line[0][i][j + 1] != 0 and board.line[0][i + 1][j] != 0 and \
                    board.line[0][i + 1][j + 1] != 0 and board.line[1][j][i] == 0 and board.line[1][j + 1][i] == 0 and \
                    board.line[1][j + 2][i] == 0:
                mid_all_t += 1
    # 循环判断中间部分纵向的短链（纵向需要判断3列2个）
    mid_all_l = 0
    for i in range(1, 3):
        for j in range(1, 2):
            if board.line[1][i][j] != 0 and board.line[1][i][j + 1] != 0 and board.line[1][i + 1][j] != 0 and \
                    board.line[1][i + 1][j + 1] != 0 and board.line[0][j][i] == 0 and board.line[0][j + 1][i] == 0 and \
                    board.line[0][j + 2][i] == 0:
                mid_all_l += 1
    return top_left_t, top_left_l, top_right_t, top_right_l, bottom_left_t, bottom_left_l, bottom_right_t, bottom_right_l, left_all_t, left_all_l, right_all_t, right_all_l, mid_all_t, mid_all_l


# 短链构造器
def sc_creat(board: Board):
    sc_list = jg_sc(board)
    # 左上角可用步数
    available_step_top_left = []
    # 1.左上角的短链构造
    if sc_list[0] != 1:
        if board.line[0][0][0] == 0:
            available_step_top_left.append((0, 0, 0))
        if board.line[0][0][1] == 0:
            available_step_top_left.append((0, 0, 1))
        if board.line[0][1][0] == 0:
            available_step_top_left.append((0, 1, 0))
        if board.line[0][1][1] == 0:
            available_step_top_left.append((0, 1, 1))
    return available_step_top_left


# 安全性判断
def decide(board: Board, x, y):
    # 定义安全性
    # 安全系数越高越安全
    # ******
    # 1 当前会有形成c型格的危险
    # ******
    print('******')
    print('安全性检查')
    print('******')
    if x == 0 and y == 0:
        # 左上角判定安全性
        top_left_security_t = 0
        top_left_security_l = 0
        top_left_safe_step = []
        if board.box[0][0] == 0:
            if board.box[0][1] == 0 and board.box[1][0] == 0:
                if board.line[0][0][1] + board.line[1][2][0] >= 2 or board.line[0][1][0] + board.line[1][2][0] >= 2:
                    top_left_security_t = 1
                    # 返回安全边（后面实现）
                    top_left_safe_step.append((1, 0, 0))
                if board.line[1][0][1] + board.line[0][2][0] >= 2 or board.line[1][1][1] + board.line[0][2][0] >= 2:
                    top_left_security_l = 1
                    # 返回安全边（后面实现）
                    top_left_safe_step.append((0, 0, 0))
        return top_left_safe_step
    if x == 0 and y == 4:
        # 右上角判定安全性
        top_right_security_t = 0
        top_right_security_l = 0
        top_right_safe_step = []
        if board.box[0][4] == 0:
            if board.box[0][3] == 0 and board.box[1][4] == 0:
                if board.line[0][0][3] + board.line[1][3][0] >= 2 or board.line[0][1][3] + board.line[1][3][0] >= 2:
                    top_right_security_t = 1
                    top_right_safe_step.append((1, 5, 0))
                if board.line[1][4][1] + board.line[0][2][4] >= 2 or board.line[1][5][1] + board.line[0][2][4] >= 2:
                    top_right_security_l = 1
                    top_right_safe_step.append((0, 0, 4))
        return top_right_safe_step
    if x == 4 and y == 0:
        # 左下角判定安全性
        bottom_left_security_t = 0
        bottom_left_security_l = 0
        bottom_left_safe_step = []
        if board.box[4][0] == 0:
            if board.box[3][0] == 0 and board.box[4][1] == 0:
                if board.line[1][0][3] + board.line[0][3][0] >= 2 or board.line[1][1][3] + board.line[0][3][0] >= 2:
                    bottom_left_security_t = 1
                    bottom_left_safe_step.append((0, 5, 0))
                if board.line[0][5][1] + board.line[1][2][4] >= 2 or board.line[0][4][1] + board.line[1][2][4] >= 2:
                    bottom_left_security_l = 1
                    bottom_left_safe_step.append((1, 0, 4))
        return bottom_left_safe_step
    if x == 4 and y == 4:
        # 右下角判定安全性
        bottom_right_security_t = 0
        bottom_right_security_l = 0
        bottom_right_safe_step = []
        if board.box[4][4] == 0:
            if board.box[3][4] == 0 and board.box[4][3] == 0:
                if board.line[1][5][3] + board.line[0][3][4] >= 2 or board.line[1][4][3] + board.line[0][3][4] >= 2:
                    bottom_right_security_t = 1
                    bottom_right_safe_step.append((0, 5, 4))
                if board.line[0][4][3] + board.line[1][3][4] >= 2 or board.line[0][5][3] + board.line[1][3][4] >= 2:
                    bottom_right_security_l = 1
                    bottom_right_safe_step.append((1, 5, 4))
        return bottom_right_safe_step
    if 1 <= x <= 3 and 1 <= y <= 3:
        # 中间部分判断安全性
        top_security = 0
        bottom_security = 0
        left_security = 0
        right_security = 0
        safe_step = []
        for i in range(1, 3):
            for j in range(1, 3):
                if i == x and j == y:
                    if board.box[i][j] == 0:
                        if board.box[i - 1][j] == 0 and board.box[i + 1][j] == 0 and board.box[i][j - 1] == 0 and \
                                board.box[i][j + 1] == 0:
                            if board.line[1][j][i - 1] + board.line[0][i - 1][j] >= 2 or board.line[1][j + 1][i - 1] + \
                                    board.line[0][i - 1][j] >= 2:
                                top_security = 1
                            if board.line[0][i + 1][j - 1] + board.line[1][j][i - 1] >= 2 or board.line[0][i][j - 1] + \
                                    board.line[1][j][i - 1] >= 2:
                                left_security = 1
                            if board.line[0][i + 1][j + 1] + board.line[1][j + 2][i] >= 2 or board.line[0][i][j + 1] + \
                                    board.line[1][j + 2][i] >= 2:
                                right_security = 1
                            if board.line[1][j][i + 1] + board.line[0][i + 2][j] >= 2 or board.line[1][j + 1][i + 1] + \
                                    board.line[0][i + 2][j] >= 2:
                                bottom_security = 1
                            if top_security == 1 and right_security == 0 and left_security == 0 and bottom_security == 0:
                                safe_step.append((0, i + 1, j))
                                safe_step.append((1, j, i))
                                safe_step.append((1, j + 1, i))
                            elif top_security == 0 and bottom_security == 1 and left_security == 0 and right_security == 0:
                                safe_step.append((0, i, j))
                                safe_step.append((1, j, i))
                                safe_step.append((1, j + 1, i))
                            elif top_security == 0 and bottom_security == 0 and left_security == 1 and right_security == 0:
                                safe_step.append((0, i, j))
                                safe_step.append((0, i + 1, j))
                                safe_step.append((0, j + 1, i))
                            elif top_security == 0 and bottom_security == 0 and left_security == 0 and right_security == 1:
                                safe_step.append((0, i, j))
                                safe_step.append((0, i + 1, j))
                                safe_step.append((1, j, i))
                            elif top_security == 1 and bottom_security == 0 and left_security == 1 and right_security == 0:
                                safe_step.append((1, j + 1, i))
                                safe_step.append((0, i + 1, j))
                            elif top_security == 1 and bottom_security == 1 and left_security == 0 and right_security == 0:
                                safe_step.append((1, j, i))
                                safe_step.append((1, j + 1, i))
                            elif top_security == 1 and bottom_security == 0 and left_security == 0 and right_security == 1:
                                safe_step.append((1, j, i))
                                safe_step.append((0, i + 1, j))
                            elif top_security == 0 and bottom_security == 1 and left_security == 1 and right_security == 0:
                                safe_step.append((0, i, j))
                                safe_step.append((1, j + 1, i))
                            elif top_security == 0 and bottom_security == 0 and left_security == 1 and right_security == 1:
                                safe_step.append((0, i, j))
                                safe_step.append((0, i + 1, j))
                            elif top_security == 0 and bottom_security == 1 and left_security == 0 and right_security == 1:
                                safe_step.append((0, i, j))
                                safe_step.append((1, j, i))
                            elif top_security == 1 and bottom_security == 1 and left_security == 1 and right_security == 0:
                                safe_step.append((1, j + 1, i))
                            elif top_security == 0 and bottom_security == 1 and left_security == 1 and right_security == 1:
                                safe_step.append((0, i, j))
                            elif top_security == 1 and bottom_security == 1 and left_security == 0 and right_security == 1:
                                safe_step.append((1, j, i))
                            elif top_security == 1 and bottom_security == 0 and left_security == 1 and right_security == 1:
                                safe_step.append((0, i + 1, j))
        return safe_step
    null_step = []
    return null_step


# 树的测试
def box_tree(board: Board):
    line = board.line
    box = board.box


def negamax(frame: Frame):
    #创建根节点
    root = TreeNode(frame.red_player, frame.blue_player, frame.red_score, frame.blue_score, frame.current_round, frame.current_board, None)
    #生成树
    root.gen_tree(root, 2)
    negamax_search(root)

    for node in root.children:
        if len(root.step) == 1:
            return root.step[0]
        if node.utility == -root.utility:
            return node.gen_step



def negamax_search(root: TreeNode):
    #如果当前节点是最终节点
    if root.is_terminal():
        # root.board.check_box(root.current_player)
        return root.evaluate_node(root)

    best_value = MIN
    for node in root.children:
        node_val = -negamax_search(node)
        best_value = max(best_value, node_val)
    root.utility = best_value
    return best_value